In this paper, we consider the sliding window model and propose two different (on-line) algorithms that approximate the items frequency in the active window. More precisely, we determine a (ϵ, δ)-additive-approximation meaning that the error is greater than ϵ only with probability δ. These solutions use a very small amount of memory with respect to the size N of the window and the number n of distinct items of the stream, namely, O(1/ϵ log 1/δ (log N + log n)) and O(1/τϵ log 1/δ(log N + log n)) bits of space, where τ is a parameter limiting memory usage. We also provide their distributed variant, i.e., Considering the sliding window functional monitoring model. We compared the proposed algorithms to each other and also to the state of the art through extensive experiments on synthetic traces and real data sets that validate the robustness and accuracy of our algorithms.
Efficiently Summarizing Data Streams over Sliding Windows / RIVETTI DI VAL CERVO, Nicolo'; Busnel, Yann; Mostefaoui, Achour. - ELETTRONICO. - (2015), pp. 151-158. (Intervento presentato al convegno 14th IEEE International Symposium on Network Computing and Applications, NCA 2015 tenutosi a Cambridge; United States nel 28 - 30 September 2015) [10.1109/NCA.2015.46].
Efficiently Summarizing Data Streams over Sliding Windows
RIVETTI DI VAL CERVO, NICOLO'
;BUSNEL, YANN;
2015
Abstract
In this paper, we consider the sliding window model and propose two different (on-line) algorithms that approximate the items frequency in the active window. More precisely, we determine a (ϵ, δ)-additive-approximation meaning that the error is greater than ϵ only with probability δ. These solutions use a very small amount of memory with respect to the size N of the window and the number n of distinct items of the stream, namely, O(1/ϵ log 1/δ (log N + log n)) and O(1/τϵ log 1/δ(log N + log n)) bits of space, where τ is a parameter limiting memory usage. We also provide their distributed variant, i.e., Considering the sliding window functional monitoring model. We compared the proposed algorithms to each other and also to the state of the art through extensive experiments on synthetic traces and real data sets that validate the robustness and accuracy of our algorithms.File | Dimensione | Formato | |
---|---|---|---|
Rivetti_Efficiently_2015.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
328.12 kB
Formato
Adobe PDF
|
328.12 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.